//
// Created by 29019 on 2020/5/7.
//

#ifndef GENERAL_SORTER_H
#define GENERAL_SORTER_H
#include <stdint.h>
#include <iostream>

using  namespace std;
template <typename  T>
class CompareHanlder{
    typedef bool (*CompareFunc) (T data1,T data2);
public:
    CompareFunc Handler(){return mHandler;};
    CompareFunc mHandler;
    CompareHanlder(CompareFunc func){
        mHandler = func;
    }

private:
    CompareHanlder(){};
};

template <typename T>
class BSTNode {
public:
    BSTNode<T>(){
        lchild = nullptr;
        rchild = nullptr;
    }
    ~BSTNode<T>(){
        if(nullptr != lchild){
            delete  lchild;
        }
        if(nullptr != rchild){
            delete  rchild;
        }
    };
    T  data;									//每个结点的数据域包括关键字项和其他信息
    struct BSTNode *lchild;
    struct BSTNode *rchild;
};

template <typename  T>
int bubblesort(T *data,uint64_t len,CompareHanlder<T> handle){
    if(nullptr == data){
        return -1;
    }
    for(uint64_t i = 0;i < len - 1;i++){
        for(uint64_t z = 0; z < len - 1 - i;z++){
            if(handle.Handler()(data[z],data[z + 1])){
                T tmp = data[z + 1];
                data[z + 1] = data[z];
                data[z] = tmp;
            }
        }
    }
}

template <typename  T>
int selectsort(T *data,uint64_t len,CompareHanlder<T> handle){
    if(nullptr == data){
        return -1;
    }
    for(uint64_t i = 0;i < len;i++){
        T biggestindex = i;
        for(uint64_t z = i; z < len ;z++){
            if(handle.Handler()(data[z],data[biggestindex])){
                biggestindex = z;
            }
        }
        T tmp = data[biggestindex];
        data[biggestindex] = data[i];
        data[i] = tmp;
    }
}

template <typename T>
void swap(T *a1,T *a2){
    T tmp = *a1;
    *a1 = *a2;
    *a2 = tmp;
}
template <typename T>
void maxHeapIfy(T unsort[], int i,int n)  //将i节点为根的堆中小的数依次上移,n表示堆中的数据个数

{
    int l = 2 * i + 1;   //i的左儿子
    int r = 2 * i + 2;  //i的右儿子
    int largest = i;   //先设置父节点和子节点三个节点中最大值的位置为父节点下标
    if (l < n && unsort[l] > unsort[largest])
        largest = l;
    if (r < n && unsort[r] > unsort[largest])
        largest = r;
    if (largest != i)    //最大值不是父节点，交换
    {
        swap(&unsort[i],&unsort[largest]);
        maxHeapIfy(unsort, largest, n);  //递归调用，保证子树也是最大堆
    }
}

template <typename T>
void buildMaxHeap(T A[], int len)  //建立最大堆
{
    std::cout <<"\r\n";
// 从最后一个非叶子节点（n/2-1）开始自底向上构建，根据完全二叉树的性质, i --肯定也是根节点。从右到左，从下到上调整。
    for (int i = len / 2 - 1; i >= 0; i--)  //从（n/2-1）调用一次maxHeapIfy就可以得到最大堆
        maxHeapIfy(A, i, len);
    for (int i = 0; i < len; i++){
       std::cout << A[i]<<" ";
    }
    std::cout <<"\r\n";
}
template <typename T>
void adjust(T arr[], int len, int index)
{
    int left = 2*index + 1;
    int right = 2*index + 2;
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx])
        maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx])
        maxIdx = right;  // maxIdx是3个数中最大数的下标
    if(maxIdx != index)                 // 如果maxIdx的值有更新
    {
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);       // 递归调整其他不满足堆性质的部分
    }

}


template <typename T>
void PreOrderTraverse(BSTNode<T> *data)
{
    if (data)
    {
        cout << data->data << " ";
        PreOrderTraverse(data->lchild);
        PreOrderTraverse(data->rchild);
    }
}
/*
 *其实整个堆排序过程中, 我们只需重复做两件事：
建堆(初始化+调整堆, 时间复杂度为O(n));
拿堆的根节点和最后一个节点交换(siftdown, 时间复杂度为O(n*log n) ).
 */
template <typename T>
int heapsort(T *data,uint64_t len,CompareHanlder<T> handle){
    buildMaxHeap(data, len);  //先建立最大堆，最大堆只能保证根节点比左右两个子树还大
    // todo
}

#endif //GENERAL_SORTER_H
